﻿using System.Collections;
using System.Collections.Generic;
using System.Runtime.InteropServices.WindowsRuntime;
using Unity.VisualScripting.Antlr3.Runtime.Collections;
using UnityEngine;


public class PathFinding
{
    Grid<PathNode> g;

    List<PathNode> openList;  //记录下一个访问的位置
    List<PathNode> closeList; //记录已经访问过的位置

    private const int MOVE_DIAGONAL_COST = 14;
    private const int MOVE_STRAIGHT_COST = 10;


    public List<PathNode> pa { get; private set; }

    public PathFinding(int width, int height,float cellSize)
    {
        g = new Grid<PathNode>(width, height, cellSize, Vector3.zero, (Grid<PathNode> g2, int x, int y) => new PathNode(x, y, g2));
        g.onGridValueChange += ChangeGridColor;
    }

    public Grid<PathNode> GetGrid()
    {
        return g;
    }

    public void ChangeGridColor(object sener, Grid<PathNode>.OnGridValueChangeEventArgs e)
    {
        PathfindingDebugStepVisual.Instance.BlockGrid(g);
    }

    public List<PathNode> FindPath(int startX, int startY, int endX, int endY)
    {
        pa = new List<PathNode>();
        float startTime = Time.realtimeSinceStartup;
        PathNode startNode = g.GetGridObject(startX, startY);
        PathNode endNode = g.GetGridObject(endX, endY);
        
        if (startNode == null || endNode == null)
        {
            return null;
        }

        openList = new List<PathNode>() { startNode };
        closeList = new List<PathNode>();

        //初始化全部位置的代价
        for (int i = 0; i < g.GetWidth(); i++)
        {
            for (int j = 0; j < g.GetHeight(); j++)
            {
                PathNode temp = g.GetGridObject(i, j);
                temp.gCost = int.MaxValue / 2;
                temp.CalculateFCost();
                temp.cameFromNode = null;
            }
        }

        startNode.gCost = 0;
        startNode.hCost = CalculateDistanceCost(startNode, endNode);
        startNode.CalculateFCost();

        //FindPath只会执行一次，那么首先把还没执行完的寻路事件给清除了
        PathfindingDebugStepVisual.Instance.ClearSnapshot();
        PathfindingDebugStepVisual.Instance.TakeSnapshot(g, startNode, openList, closeList);


        while (openList.Count > 0)
        {
            //遍历可以达到的位置，找最小代价
            PathNode curNode = GetLowestNode(openList);

            if (closeList.Contains(curNode))
            {
                continue;
            }

            if (curNode == endNode)
            {
                List<PathNode> pathList = GetPathList(endNode);

                PathfindingDebugStepVisual.Instance.TakeSnapshot(g, endNode, openList, closeList);

                //最后把不是正确路径的给抹成灰色
                PathfindingDebugStepVisual.Instance.TakeFinalSnapshot(g, pathList);

                Debug.Log(Time.realtimeSinceStartup - startTime);

                pa = pathList;
                return pathList;
            }
            
            //删除当前正在遍历的节点，以防再次遍历到
            openList.Remove(curNode);
            closeList.Add(curNode);

            foreach (PathNode next in GetNeibourList(curNode))
            {
                if (!next.isWalkable)
                {
                    closeList.Add(next);
                }

                if (closeList.Contains(next))
                {
                    continue;
                }

                int allGCost = curNode.gCost + CalculateDistanceCost(curNode, next);
                if (allGCost < next.gCost)
                {
                    next.cameFromNode = curNode;
                    next.gCost = allGCost;
                    next.hCost = CalculateDistanceCost(next, endNode);
                    next.CalculateFCost();

                    if (!openList.Contains(next))
                    { 
                        openList.Add(next);
                    }
                }

                //不管是不是正确路径，都变成下一个事件存入事件列表中
                PathfindingDebugStepVisual.Instance.TakeSnapshot(g, next, openList, closeList);
            }

        }

        pa = null;
        return null;
    }


    //计算距离代价
    public int CalculateDistanceCost(PathNode cur, PathNode next)
    {
        int x = Mathf.Abs(cur.x - next.x);
        int y = Mathf.Abs(cur.y - next.y);
        //因为可以斜角走，所以令|x-y|可以得到最佳的直线移动距离
        int remaining = Mathf.Abs(x - y);

        return remaining * MOVE_STRAIGHT_COST + Mathf.Min(x, y) * MOVE_DIAGONAL_COST;
    }

    public PathNode GetLowestNode(List<PathNode> openList)
    {
        PathNode lowestNode = openList[0];

        for (int i = 1; i < openList.Count; i++)
        {
            if (openList[i].fCost<lowestNode.fCost)
            { 
                lowestNode = openList[i];
            }
        }

        return lowestNode;
        
    }

    public List<PathNode> GetPathList(PathNode node)
    {
        List<PathNode> res = new List<PathNode>();
        res.Add(node);

        while (node.cameFromNode != null)
        { 
            res.Add(node.cameFromNode);
            node = node.cameFromNode;
        }
        res.Reverse();
        return res;
    }

    public List<PathNode> GetNeibourList(PathNode node)
    {
        List<PathNode> res = new List<PathNode>();

        int curX = node.x;
        int curY = node.y;

        //上 左上 右上
        if (curY + 1 < g.GetHeight())
        {
            res.Add(g.GetGridObject(curX, curY + 1));

            if (curX - 1 >= 0)
            {
                res.Add(g.GetGridObject(curX - 1, curY + 1));
            }

            if (curX + 1 < g.GetWidth())
            {
                res.Add(g.GetGridObject(curX +1, curY + 1));
            }
        }

        //下 左下 右下
        if (curY - 1 >= 0)
        {
            res.Add(g.GetGridObject(curX, curY - 1));

            if (curX - 1 >= 0)
            {
                res.Add(g.GetGridObject(curX - 1, curY - 1));
            }

            if (curX + 1 < g.GetWidth())
            {
                res.Add(g.GetGridObject(curX + 1, curY - 1));
            }
        }

        //左 右
        if (curX - 1 >= 0)
        {
            res.Add(g.GetGridObject(curX - 1, curY));
        }
        
        if (curX + 1 < g.GetWidth())
        {
            res.Add(g.GetGridObject(curX + 1, curY));
        }


        return res;
    }

    public PathNode GetPathNode(int x, int y)
    {
        return g.GetGridObject(x, y);
    }
}
